// Josephus
#include <vector>
#include <iostream>

using namespace std;

// n - 参与游戏的人
// 返回只有一个人的时候，这个人的编号
int josephus(int n) {
  // people 的索引，就是人的编号
  vector<int> people(n, 0);
  int c = 0;    // 记录出局的人数
  int flag = 0; // flag = 1 报 1，反之报 0
  int i = 0;    // 下一个报数的人的编号

  while (c < n - 1) {
    // 只有没出局的人才能参加游戏
    if (people[i] == 0) {
      if (flag == 1) {
        people[i] = 1;
        ++c;
      }

      // ^ 按位异或操作符
      // 按位异或针对二进制数字而言的
      // 0b1101
      // 0b0101 ^ 对应的二进制位相同为 0，不同为 1
      // -------
      // 0b1000
      //
      // 0b0000
      // 0b0001
      flag ^= 1;
    }

    // 找到下一个报数的人的编号
    i = i + 1;
    if (i == n) {
      i = 0;
    }
  }

  // 怎么能找到最后一个人的编号？
  int result = 0;
  for (int i = 0; i < people.size(); ++i) {
    if (people[i] == 0) {
      result = i;
      break;
    }
  }

  return result;
}

/*
x = 4

4 = 0b0100
3 = 0b0011 &
------------
0b0100
f(4) => 1
0b0101
f(5) => 2

0b0101
0b0100

for (; 5; 5 &= 4) ret = 1
for (; 4; 4 &= 3) ret = 2
for (; 0;) => X

统计 x 的二进制里 1 的个数
*/
int f(int x) {
  int ret = 0;

  for (; x; x &= x - 1) {
    ret++;
  }

  return ret;
}

// 4 = 0b0100
//-4 = 0b1011 + 1 = 0b1100

// 1 = 0b0001
// -1 = 0b1110 + 1 = 0b1111 => 15
//                          => -1

// g(x) => 保留 x 的最低二进制位
// g(4) 0b0100 => 0b0100
// g(5) 0b0101 => 0b0001
// g(6) 0b0110 => 0b0010
// 0110
// 1010
// ------
// 0010

int g(int x) {
  return x & -x;
}



int main(int argc, char const *argv[])
{
  /* code */
  // 按位与操作 &
  // 0b1001
  // 0b1101 & 只有对应二进制位都是 1 的时候结果是 1，否则是 0
  // --------
  // 0b1001
  cout << f(511998) + g(511998) << endl;
  cout << josephus(11) << endl;

  int a = 0b1111; // -1
  unsigned int b = 0b1111; // 15

  cout << a << endl << b << endl;
  return 0;
  //                 商     余数
  // 511998 / 2   
}
